package Lee_code;

public class Lee_322
{
    int max;
    int target;
    public int coinChange(int[] coins, int amount)
    {
        target = amount;
        max = 0;
        dfs(0, 0, coins);

        return max;
    }

    private void dfs(int cur_sum, int cur_num, int[] coins) {
        if (cur_num==target) {
            max = Math.max(max, cur_num);
            return;
        }
        if (cur_sum>target)
            return;
        for (int coin : coins) {
            dfs(cur_sum+coin,cur_num+1, coins);
        }
    }
}
